import java.util.*;

public class Tree {
    public static class TreeNode {
        public int val;
        public TreeNode left;
        public TreeNode right;

        public TreeNode(int val) {
            this.val = val;
        }
    }
//    public List<List<Character>> levelOrder(TreeNode root) {
//        //创建二维数组列表：储存每层节点
//        List<List<Character>> ret = new ArrayList<>();
//        //空树处理
//        if(root == null){
//            return ret;
//        }
//        //创建队列
//        Queue<TreeNode> queue = new LinkedList<>();
//        //进队
//        queue.offer(root);
//        //外层循环：处理每一层
//        while(!queue.isEmpty()){
//            //当前层存储列表
//            List<Character> curRow = new ArrayList<>();
//            //当前层节点树
//            int size = queue.size();
//            //内层循环：处理当前层
//            while(size != 0){
//                //出队
//                TreeNode cur = queue.poll();
//                //存入当前层
//                curRow.add(cur.val);
//                if(cur.left != null){
//                    queue.offer(cur.left);
//                }
//                if(cur.right != null){
//                    queue.offer(cur.right);
//                }
//                size--;
//            }
//            //将当前层加入结果列表
//            ret.add(curRow);
//        }
//        return ret;
//    }
//public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
//    //当前节点为空，直接返回null
//    if(root == null){
//        return null;
//    }
//    //当前节点是p或者q，返回当前节点（祖先）
//    if(root == p || root == q){
//        return root;
//    }
//    //递归探索左子树，找到p和q的最近祖先
//    TreeNode leftRet = lowestCommonAncestor(root.left, p, q);
//    //递归探索右子树，找到p和q的最近祖先
//    TreeNode rightRet = lowestCommonAncestor(root.right, p, q);
//    //左子树和右子树都找到
//    if(leftRet != null && rightRet != null){
//        return root;
//        //左子树找到
//    }else if(leftRet != null){
//        return leftRet;
//    }else{//右子树找到
//        return rightRet;
//    }
//}
//找到root到node路径上所有节点存储到栈中
    public boolean getPath(TreeNode root, TreeNode node, Stack<TreeNode> stack) {
        if(root == null){
            return false;
        }
        //将当前节点压入路径
        stack.push(root);
        //找到目标节点
        if(root == node){
            return true;
        }
        //递归搜索左子树
        boolean flg = getPath(root.left,node,stack);
        if(flg){
            return true;
        }
        //递归搜索右子树
        flg = getPath(root.right,node,stack);
        if(flg){
            return true;
        }
        //左右子树都没找到，弹出当前节点
        stack.pop();
        return false;
    }
    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q){
        if(root == null){
            return null;
        }
        //找到跟到p和q的路径
        Stack<TreeNode> stackp = new Stack<>();
        Stack<TreeNode> stackq = new Stack<>();
        getPath(root,p,stackp);
        getPath(root,q,stackq);
        //对齐两个栈长度
        int sizep = stackp.size();
        int sizeq = stackq.size();
        int size = sizep-sizeq;
        if(size>0){
            //stacp更长，弹出多余元素
            while (size != 0){
                stackp.pop();
                size--;
            }
        }else {
            ////stacq更长，弹出多余元素
            size = sizeq-sizep;
            while (size != 0){
                stackq.pop();
                size--;
            }
        }
        //此时两个栈大小一样，//同时弹出栈顶，找到相同的
        while (!stackp.isEmpty()&&!stackq.isEmpty()){
            if(stackp.peek().equals(stackq.peek())){
                return stackp.peek();
            }
            stackp.pop();
            stackq.pop();
        }
        return null;
    }
}

